package org.example.sword2offer.primary;

/**
 *  * @author: lynn
 *  * @description:二叉树的下一个结点
 *   给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 *   注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 *   解析: https://blog.csdn.net/zhuibushixi/article/details/114761774
 *  * @date: 2021/3/24 14:15
 *  * @version 1.0.0
 *  
 */
public class Q56_GetNextTreeNode {

    public static void main(String[] args) {

    }

    /**
     * 由于中序遍历来到某个结点后，首先会接着遍历它的右子树，
     * 如果它没有右子树则会回到祖先结点中将它当做左子树上的结点的那一个，因此有如下分析：
     *
     * 1.如果当前结点有右子树，那么其后继结点就是其右子树上的最左结点
     * 2.如果当前结点没有右子树，那么其后继结点就是其祖先结点中，将它当做左子树上的结点的那一个。
     */
    private static TreeLinkNode GetNext(TreeLinkNode pNode){
        if (pNode==null){
            return null;
        }
        //如果有右子树
        if(pNode.right!=null){
            TreeLinkNode p=pNode.right;
            while (p.left!=null){
                p=p.left;
            }
            return p;
        }else {
            //如果没有右子树，向上查找第一个当前结点是父结点的左孩子的结点
            TreeLinkNode p = pNode.next;
            while(p != null && pNode != p.left){
                pNode = p;
                p = p.next;
            }
            if(p != null && pNode == p.left){
                return p;
            }
            return null;
        }
    }


    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
}
